๐Ÿ‘ฉโ€๐Ÿ’ป 14499. ์ฃผ์‚ฌ์œ„ ๊ตด๋ฆฌ๊ธฐ

@Seongukbaek Posted March 28, 2022 ยท Updated March 28, 2022 ยท 7 min read

๋ฌธ์ œ

ํฌ๊ธฐ๊ฐ€ Nร—M์ธ ์ง€๋„๊ฐ€ ์กด์žฌํ•œ๋‹ค. ์ง€๋„์˜ ์˜ค๋ฅธ์ชฝ์€ ๋™์ชฝ, ์œ„์ชฝ์€ ๋ถ์ชฝ์ด๋‹ค. ์ด ์ง€๋„์˜ ์œ„์— ์ฃผ์‚ฌ์œ„๊ฐ€ ํ•˜๋‚˜ ๋†“์—ฌ์ ธ ์žˆ์œผ๋ฉฐ, ์ฃผ์‚ฌ์œ„์˜ ์ „๊ฐœ๋„๋Š” ์•„๋ž˜์™€ ๊ฐ™๋‹ค. ์ง€๋„์˜ ์ขŒํ‘œ๋Š” (r, c)๋กœ ๋‚˜ํƒ€๋‚ด๋ฉฐ, r๋Š” ๋ถ์ชฝ์œผ๋กœ๋ถ€ํ„ฐ ๋–จ์–ด์ง„ ์นธ์˜ ๊ฐœ์ˆ˜, c๋Š” ์„œ์ชฝ์œผ๋กœ๋ถ€ํ„ฐ ๋–จ์–ด์ง„ ์นธ์˜ ๊ฐœ์ˆ˜์ด๋‹ค.

2 4 1 3 5 6

์ฃผ์‚ฌ์œ„๋Š” ์ง€๋„ ์œ„์— ์œ— ๋ฉด์ด 1์ด๊ณ , ๋™์ชฝ์„ ๋ฐ”๋ผ๋ณด๋Š” ๋ฐฉํ–ฅ์ด 3์ธ ์ƒํƒœ๋กœ ๋†“์—ฌ์ ธ ์žˆ์œผ๋ฉฐ, ๋†“์—ฌ์ ธ ์žˆ๋Š” ๊ณณ์˜ ์ขŒํ‘œ๋Š” (x, y) ์ด๋‹ค. ๊ฐ€์žฅ ์ฒ˜์Œ์— ์ฃผ์‚ฌ์œ„์—๋Š” ๋ชจ๋“  ๋ฉด์— 0์ด ์ ํ˜€์ ธ ์žˆ๋‹ค.

์ง€๋„์˜ ๊ฐ ์นธ์—๋Š” ์ •์ˆ˜๊ฐ€ ํ•˜๋‚˜์”ฉ ์“ฐ์—ฌ์ ธ ์žˆ๋‹ค. ์ฃผ์‚ฌ์œ„๋ฅผ ๊ตด๋ ธ์„ ๋•Œ, ์ด๋™ํ•œ ์นธ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๊ฐ€ 0์ด๋ฉด, ์ฃผ์‚ฌ์œ„์˜ ๋ฐ”๋‹ฅ๋ฉด์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๊ฐ€ ์นธ์— ๋ณต์‚ฌ๋œ๋‹ค. 0์ด ์•„๋‹Œ ๊ฒฝ์šฐ์—๋Š” ์นธ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๊ฐ€ ์ฃผ์‚ฌ์œ„์˜ ๋ฐ”๋‹ฅ๋ฉด์œผ๋กœ ๋ณต์‚ฌ๋˜๋ฉฐ, ์นธ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๋Š” 0์ด ๋œ๋‹ค.

์ฃผ์‚ฌ์œ„๋ฅผ ๋†“์€ ๊ณณ์˜ ์ขŒํ‘œ์™€ ์ด๋™์‹œํ‚ค๋Š” ๋ช…๋ น์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ฃผ์‚ฌ์œ„๊ฐ€ ์ด๋™ํ–ˆ์„ ๋•Œ ๋งˆ๋‹ค ์ƒ๋‹จ์— ์“ฐ์—ฌ ์žˆ๋Š” ๊ฐ’์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ฃผ์‚ฌ์œ„๋Š” ์ง€๋„์˜ ๋ฐ”๊นฅ์œผ๋กœ ์ด๋™์‹œํ‚ฌ ์ˆ˜ ์—†๋‹ค. ๋งŒ์•ฝ ๋ฐ”๊นฅ์œผ๋กœ ์ด๋™์‹œํ‚ค๋ ค๊ณ  ํ•˜๋Š” ๊ฒฝ์šฐ์—๋Š” ํ•ด๋‹น ๋ช…๋ น์„ ๋ฌด์‹œํ•ด์•ผ ํ•˜๋ฉฐ, ์ถœ๋ ฅ๋„ ํ•˜๋ฉด ์•ˆ ๋œ๋‹ค.

์ž…, ์ถœ๋ ฅ

์ž…๋ ฅ

  • ์ฒซ์งธ ์ค„์— ์ง€๋„์˜ ์„ธ๋กœ ํฌ๊ธฐ N, ๊ฐ€๋กœ ํฌ๊ธฐ M (1 โ‰ค N, M โ‰ค 20), ์ฃผ์‚ฌ์œ„๋ฅผ ๋†“์€ ๊ณณ์˜ ์ขŒํ‘œ x, y(0 โ‰ค x โ‰ค N-1, 0 โ‰ค y โ‰ค M-1), ๊ทธ๋ฆฌ๊ณ  ๋ช…๋ น์˜ ๊ฐœ์ˆ˜ K (1 โ‰ค K โ‰ค 1,000)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.
  • ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ์ง€๋„์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๊ฐ€ ๋ถ์ชฝ๋ถ€ํ„ฐ ๋‚จ์ชฝ์œผ๋กœ, ๊ฐ ์ค„์€ ์„œ์ชฝ๋ถ€ํ„ฐ ๋™์ชฝ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ์ฃผ์‚ฌ์œ„๋ฅผ ๋†“์€ ์นธ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๋Š” ํ•ญ์ƒ 0์ด๋‹ค. ์ง€๋„์˜ ๊ฐ ์นธ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๋Š” 10 ๋ฏธ๋งŒ์˜ ์ž์—ฐ์ˆ˜ ๋˜๋Š” 0์ด๋‹ค.
  • ๋งˆ์ง€๋ง‰ ์ค„์—๋Š” ์ด๋™ํ•˜๋Š” ๋ช…๋ น์ด ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ๋™์ชฝ์€ 1, ์„œ์ชฝ์€ 2, ๋ถ์ชฝ์€ 3, ๋‚จ์ชฝ์€ 4๋กœ ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

  • ์ด๋™ํ•  ๋•Œ๋งˆ๋‹ค ์ฃผ์‚ฌ์œ„์˜ ์œ— ๋ฉด์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ๋งŒ์•ฝ ๋ฐ”๊นฅ์œผ๋กœ ์ด๋™์‹œํ‚ค๋ ค๊ณ  ํ•˜๋Š” ๊ฒฝ์šฐ์—๋Š” ํ•ด๋‹น ๋ช…๋ น์„ ๋ฌด์‹œํ•ด์•ผ ํ•˜๋ฉฐ, ์ถœ๋ ฅ๋„ ํ•˜๋ฉด ์•ˆ ๋œ๋‹ค.

๐Ÿ“ Logic

class Dice { int[][] map; int[] commands; int[] numbers = new int[6]; int[] rangeX = { 0, 0, -1, 1 }; int[] rangeY = { 1, -1, 0, 0 }; int N, M, K; int top = 0, front = 4, east = 2; ... }
  • ์ฃผ์‚ฌ์œ„์™€ ์ง€๋„์˜ ์ •๋ณด๋ฅผ ์ €์žฅํ•˜๋Š” ํด๋ž˜์Šค
  • top, front, east ์ •๋ณด๋ฅผ ๊ณ„์† ๋ณ€๊ฒฝํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ฃผ์‚ฌ์œ„์˜ ์ˆซ์ž ์ •๋ณด๋ฅผ ์ถ”์ ํ•œ๋‹ค.
public void game(int x, int y) { for (int i = 0; i < K; i++) { int nx = x + rangeX[commands[i] - 1]; int ny = y + rangeY[commands[i] - 1]; if (isInTheMap(nx, ny)) continue; x = nx; y = ny; rollDice(commands[i] - 1); if (map[x][y] == 0) { map[x][y] = numbers[5 - top]; } else { numbers[5 - top] = map[x][y]; map[x][y] = 0; } System.out.println(numbers[top]); } }
  • ๋ช…๋ น์–ด์— ๋”ฐ๋ผ ์ง€๋„์—์„œ์˜ ์ฃผ์‚ฌ์œ„ ์œ„์น˜๋ฅผ ๋ณ€๊ฒฝ์‹œํ‚จ๋‹ค.

    • ์ง€๋„ ๋ฒ”์œ„ ์•ˆ์ธ ๊ฒฝ์šฐ๋งŒ ์ฃผ์‚ฌ์œ„ ์ •๋ณด๋ฅผ ์ˆ˜์ •ํ•˜๊ณ , ์ƒ๋‹จ์˜ ์ˆซ์ž๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.
private void rollDice(int command) { int t, e, f; t = top; e = east; f = front; switch (command) { case 0: top = 5 - e; east = t; break; case 1: top = e; east = 5 - t; break; case 2: top = f; front = 5 - t; break; case 3: top = 5 - f; front = t; } }
  • ์ฃผ์‚ฌ์œ„์˜ top, front, east ์ •๋ณด๋ฅผ ์—…๋ฐ์ดํŠธํ•˜๋Š” ๋ฉ”์†Œ๋“œ

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; class Dice { int[][] map; int[] commands; int[] numbers = new int[6]; int[] rangeX = { 0, 0, -1, 1 }; int[] rangeY = { 1, -1, 0, 0 }; int N, M, K; int top = 0, front = 4, east = 2; public Dice(int N, int M, int K) { this.N = N; this.M = M; this.K = K; map = new int[N][M]; commands = new int[K]; } public void game(int x, int y) { for (int i = 0; i < K; i++) { int nx = x + rangeX[commands[i] - 1]; int ny = y + rangeY[commands[i] - 1]; if (isInTheMap(nx, ny)) continue; x = nx; y = ny; rollDice(commands[i] - 1); if (map[x][y] == 0) { map[x][y] = numbers[5 - top]; } else { numbers[5 - top] = map[x][y]; map[x][y] = 0; } System.out.println(numbers[top]); } } private boolean isInTheMap(int x, int y) { return (x < 0 | x >= N | y < 0 | y >= M); } private void rollDice(int command) { int t, e, f; t = top; e = east; f = front; switch (command) { case 0: top = 5 - e; east = t; break; case 1: top = e; east = 5 - t; break; case 2: top = f; front = 5 - t; break; case 3: top = 5 - f; front = t; } } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); int N = line[0], M = line[1], x = line[2], y = line[3], K = line[4]; Dice dice = new Dice(N, M, K); for (int i = 0; i < N; i++) dice.map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); dice.commands = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); dice.game(x, y); br.close(); } }

โœ๏ธ Review

  • ๋‹ค๋ฅธ ๊ตฌํ˜„์€ ๋ชจ๋‘ ์‰ฌ์› ๋Š”๋ฐ, rollDice() ๊ตฌํ˜„์ด ์ œ์ผ ์–ด๋ ค์› ๋‹ค.

    • ์›๋ž˜๋Š” ๋ช…๋ น์–ด๊ฐ€ ์ฃผ์–ด์ง€๋ฉด, ์ „์—ญ์œผ๋กœ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” bottom์˜ ์ •๋ณด๋ฅผ ์—…๋ฐ์ดํŠธํ•˜๋Š” ๋ฐฉ์‹์„ ์‚ฌ์šฉํ•˜๋ ค ํ–ˆ๋Š”๋ฐ, ์•„๋ฌด๋ฆฌ ์ƒ๊ฐํ•ด๋„ ์•ˆ๋˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋งŽ์€ ๊ฒƒ ๊ฐ™์•„ ๊ฒŒ์‹œํŒ์„ ์ฐธ๊ณ ํ–ˆ๋‹ค.

๐Ÿ“• ์ถœ์ฒ˜

Baekjoon : https://www.acmicpc.net/problem/14499

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€